Higher-integration IC's (integrated circuits) and lower costs have allowed for increasingly complex graphics systems in personal computers (PCs). The two-dimensional dimensional `blackboard` of yesterday's PC's monitor is coming to life as three-dimensional objects are rendered in real-time using 3D graphics engines. Realistic-looking objects are rendered by extending the basic pixel (picture element) to include texture attributes comprised of texels (texture elements).
Complex calculations are required to transform and render 3D objects on the PC's two-dimensional screen. These objects are often rendered with surface textures. These textures are defined by texture maps. Texture maps are 2 dimensional arrays of pixels, or texels, that are transformed onto the surface in order to render finer detail.
The texture map describes the texture pattern of the surface as it appears to a viewer directly over the surface at a 90-degree normal to the surface. However, when a surface is viewed at an oblique angle, the surface texture is compressed. If viewed through a parallel projection, meaning the eye is at infinity, the compression is linear across the screen. However, if viewed through a perspective projection, meaning the eye is at a finite distance from the screen, the compression is non-linear. Thus some perspective correction is needed. This correction is accomplished by altering the address of the texel selected from the texture map.
FIG. 1 shows a texture map. The pixels in the texture map that form the surface pattern are arranged in a 2-dimensional coordinate space (u,v). One of the pixels in the texture map is selected by calculating the (u,v) coordinate of the texture map from the non-perspective-corrected pixel coordinates.
The 3D graphics engine generates a non-corrected coordinate that corresponds to (u/w, v/w). The (u,v) coordinate is obtained by multiplying u/w and v/w by w. However, w is not directly known. Instead, the reciprocal of w, called rw, is generated by the 3D engine or the applications-programming interface (API) along with (u/w, v/w). From rw, (u,v) is calculated as u=(u/w)*(1/rw) and v=(v/w)*(1/rw). The reciprocal of rw, 1/rw, must be calculated. The perspective for each pixel is corrected by the rw value.
Perspective correction thus requires the generation of the reciprocal of the rw value. FIG. 2 highlights that w is obtained by performing a reciprocal function on the rw input. Then the reciprocal (w) is multiplied by the coordinates u/w and v/w to obtain the (u,v) coordinate for the texture map. Often a large table in memory such as table lookup 10 is used to perform directly the reciprocal function. Table lookups are desirable since the complex calculations can be performed ahead of time and stored in the table for all possible input values. Thus arithmetic logic circuits are not needed for the reciprocal function.
Unfortunately, reciprocal functions produce a large range of outputs. The rw value can itself be any number from near zero to 2.sup.16 for a 16-bit rw. Values of rw that are near zero produce very large reciprocals. For example, the reciprocal of 0.001 is 1000, while the reciprocal of 0.000001 is 1,000,000. On the other hand, the reciprocal of 2.sup.15 is 2.sup.-15, a very small number. The wide dynamic range of the reciprocal function presents a challenge when using lookup tables, since the tables can require many entries, requiring a large and expensive memory.
Although the rw, u/w, and v/w values are provided as 32-bit fixed-point variables, these could be converted to a floating-point format to more efficiently perform the reciprocal function. However, standard floating point formats may require very expensive mechanization.
What is desired is a reciprocal generator for perspective correction of texture maps in a 3D graphics system. It is desired to minimize the transistor count associated with the implementation while maintaining sufficient fidelity in the output in order to avoid aliasing effects. It is desired to maintain a high pipeline throughput rate for each pixel while minimizing the transistor count. It is desired to minimize the size of a lookup table for a reciprocal function. It is desired to efficiently organize entries in the lookup table to provide sufficient precision over a large dynamic range of inputs and outputs. A better approximation of a reciprocal function is desired when using a limited-size lookup table and attend antiogic circuits. A high-speed reciprocal generator that uses a lookup table and a minimal set of logic circuits and operates over a wide dynamic range is desired.